#include<iostream>
#include<time.h>
using namespace std;

const int NUMBER_COUNT = 20;

void initializeNumbers( int numbers[] )
{
	for(int i = 0; i < NUMBER_COUNT; i++)
	{
		numbers[i] = rand()%100 + 1;
	}
}
void displayNumbers( int numbers[] )
{
	for(int i = 0; i < NUMBER_COUNT; i++)
	{
		cout << numbers[i] << endl;
	}
}

void sortNumbers( int list[], int size)
{	
	int leftList[NUMBER_COUNT];
	int rightList[NUMBER_COUNT];
	int leftSize = 0;
	int rightSize = 0;
	int pivot = list[0];

	for(int i = 1; i < size; i++)
	{
		if(list[i] < pivot)
		{
			leftList[leftSize] = list[i];
			leftSize++;
		}
		else
		{
			rightList[rightSize] = list[i];
			rightSize++;
		}
	}

	if(leftSize >= 2)
	{
		sortNumbers(leftList, leftSize);
	}
	if(rightSize >= 2)
	{
		sortNumbers(rightList, rightSize);
	}

	int i = 0;
	for(int l = 0; l < leftSize; l++)
	{
		list[i] = leftList[l];
		i++;
	}
	list[i] = pivot;
	i++;
	for(int l = 0; l < rightSize; l++)
	{
		list[i] = rightList[l];
		i++;
	}


}

void main()
{
	srand(time(NULL));
	int numbers[NUMBER_COUNT];
	initializeNumbers(numbers);
	displayNumbers(numbers);
	cout << endl << endl;
	sortNumbers(numbers, NUMBER_COUNT);
	displayNumbers(numbers);
}